/*
 * @lc app=leetcode.cn id=90 lang=cpp
 *
 * [90] 子集 II
 *
 * https://leetcode-cn.com/problems/subsets-ii/description/
 *
 * algorithms
 * Medium (63.44%)
 * Likes:    817
 * Dislikes: 0
 * Total Accepted:    196.9K
 * Total Submissions: 310.2K
 * Testcase Example:  '[1,2,2]'
 *
 * 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
 * 
 * 解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
 * 
 * 
 * 
 * 
 * 
 * 示例 1：
 * 
 * 
 * 输入：nums = [1,2,2]
 * 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
 * 
 * 
 * 示例 2：
 * 
 * 
 * 输入：nums = [0]
 * 输出：[[],[0]]
 * 
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * 1 
 * -10 
 * 
 * 
 * 
 * 
 */

// @lc code=start
class Solution {
// // 用startIndex来进行去重操作
// private:
//     vector<int> path;
//     vector<vector<int>> res;
//     void backtracking(const vector<int>& nums, int startIndex) {

//         // 收集每一个节点
//         res.push_back(path);

//         if(startIndex > nums.size()) return;

//         for (int i = startIndex; i < nums.size(); i++) {
//             // 去重
//             if(i > startIndex && nums[i] == nums[i-1]) continue;
            
//             path.push_back(nums[i]);
//             backtracking(nums, i+1);
//             path.pop_back();
//         }
//     }
// public:
//     vector<vector<int>> subsetsWithDup(vector<int>& nums) {
//         path.clear();
//         res.clear();
//         sort(nums.begin(), nums.end());
//         backtracking(nums, 0);
//         return res;
//     }

// 用used数组来进行去重操作
private:
    vector<int> path;
    vector<vector<int>> res;
    void backtracking(const vector<int>& nums, int startIndex, vector<bool>& used) {

        // 收集每一个节点
        res.push_back(path);

        if(startIndex > nums.size()) return;

        for (int i = startIndex; i < nums.size(); i++) {
            // 去重
            if(i > startIndex && nums[i] == nums[i-1] && used[i] == false) continue;
            
            used[i] = true;
            path.push_back(nums[i]);
            backtracking(nums, i+1, used);
            path.pop_back();
            used[i] = false;
        }
    }
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        path.clear();
        res.clear();
        sort(nums.begin(), nums.end());
        vector<bool> used(nums.size(), false);
        backtracking(nums, 0, used);
        return res;
    }

};
// @lc code=end

